A variable neighborhood search algorithm with reinforcement learning for a real-life periodic vehicle routing problem with time windows and open routes

Chen, Binhui; Qu, Rong; Bai, Ruibin; Laesanklang, Wasakorn

Abstract

Based on a real-life container transport problem, a model of Open Periodic Vehicle Routing Problem with Time Windows (OPVRPTW) is proposed in this paper. In a wide planning horizon, which is divided into a number of shifts, a fixed number of trucks are scheduled to complete container transportation tasks between terminals subject to time constraints. In this problem, the routes traveled by trucks are open, as returning to the starting depot is not required in every single shift but every two shifts.

Our study shows that it is unrealistic to address this large scale and nonlinearly constrained problem with exact search methods. A Reinforcement Learning Based Variable Neighbourhood Search algorithm (VNSRLS) is developed for OPVRPTW. The initial solution is constructed with an urgency level-based insertion heuristic, while different insertion selection strategies are compared. In the local search phase of VNS-RLS, reinforcement learning is used to guide the search, adjusting the probabilities of operators being invoked adaptively according to the change of generated solutions’ feasibility and quality. In addition, the impact of sampling neighbourhood space in single solution-based algorithms is also investigated. Three indicators are designed in the proposed Sampling module to set the starting configuration of local search.

Experiment results on different sizes of real and artificial benchmark instances show that, the proposed Sampling scheme and feasibility indicator decrease the infeasible rate during the search. However, Sampling’s contribution to solution quality improvement is not significant in this single solution-based algorithm. Comparing to the exact search and two state-of-the-art algorithms, VNS-RLS produces promising results

Citation

Chen, B., Qu, R., Bai, R., & Laesanklang, W. (2020). A variable neighborhood search algorithm with reinforcement learning for a real-life periodic vehicle routing problem with time windows and open routes. RAIRO: Operations Research, 54(5), 1467-1494. https://doi.org/10.1051/ro/2019080

• Journal Article Type: Article
• Acceptance Date: Aug 14, 2019
• Online Publication Date: Aug 30, 2019
• Publication Date: 2020-09
• Deposit Date: Jan 9, 2020
• Publicly Available Date: Jan 13, 2020
• Journal: RAIRO: Operations Research
• Print ISSN: 0399-0559
• Electronic ISSN: 1290-3868
• Publisher: EDP Sciences
• Peer Reviewed: Peer Reviewed
• Volume: 54
• Issue: 5
• Pages: 1467-1494
• DOI: https://doi.org/10.1051/ro/2019080
• Keywords: Open Periodic Vehicle Routing Problem with Time Windows, Adaptive Operator Selection, Metaheuristics, Variable Neighbourhood Search
• Public URL: https://nottingham-repository.worktribe.com/output/3440518
• Publisher URL: https://www.rairo-ro.org/component/article?access=doi&doi=10.1051/ro/2019080
• Additional Information: The original publication is available at www.rairo-ro.org. Copyright / Published by: EDP Sciences